package com.wrial.simple;
/*
 * @Author  Wrial
 * @Date Created in 9:56 2020/7/26
 * @Description 树的最高层次
 */

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LeetCode_559 {

    // 递归算法
//    public int maxDepth(Node root) {
//        //如果root为null就为0不为空就为1，然后在看有没有子节点由此递归
//        if (root==null) return 0;
//        int depth = 1;
//        if (root.children.size()>0){
//            List<Node> nodeList = root.children;
//            for (Node node : nodeList) {
//                // 各个子节点的最大深度+1和父节点当前的depth（遍历过程中一直更新）比较
//                depth = Math.max(depth, maxDepth(node) + 1);
//            }
//        }
//        return depth;
//    }
    //BFS
    public int maxDepth(Node root) {  //层序遍历解法
        if(root == null)
            return 0;
        if(root.children.size() == 0)
            return 1;
        int depth = 0;
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while(!queue.isEmpty()){
            //每次都处理一层的节点
            int count = queue.size();
            depth++;
            while(count > 0){
                Node node = queue.poll();
                if(node.children.size() != 0)
                    queue.addAll(node.children);
                //当count为0时也就是当前层处理完的时候
                count--;
            }
        }
        return depth;
    }

    class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    ;
}
